package com.zx._12_算法.排序;

import com.zx._12_算法.Arrs.IAS;
import com.zx._12_算法.Nums;
import lombok.extern.slf4j.Slf4j;


/**
 * 选择排序： https://www.runoob.com/w3cnote/quick-sort-2.html
 *
 * 时间复杂度：O(n*logn)
 */
@Slf4j
public class Sort6_快速排序 implements IAS {


    public static void sort(int[] arr, int begin, int end) {
        int left = begin;
        int right = end;

        while (left < right) {
            int base = arr[left];
            // 从序列右端开始，向左遍历，直到找到小于base的数
            while (left < right && arr[right] >= base) {
                right--;
            }
            // 找到了比base小的元素，将这个元素放到最左边的位置
            if (arr[right] < base) {
                Nums.swap(arr, right, left);
            }
            // 从序列左端开始，向右遍历，直到找到大于base的数
            while (left < right && arr[left] <= base) {
                left++;
            }
            // 找到了比base大的元素，将这个元素放到最右边的位置
            if (arr[left] > base) {
                Nums.swap(arr, right, left);
            }
        }
        // begin ~ left-1 就是 比left所有小的数据
        if (begin < left) {
            sort(arr, begin, left - 1);
        }
        // right + 1 ~ end 就是 比right大的数据
        if (right < end) {
            sort(arr, right + 1, end);
        }
    }

    @Override
    public void sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }
}
